package tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class isSubtree {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null){
            return false;
        }
        if (commpare(root, subRoot)) {
            return true;
        }
        // 如果当前树与 subRoot 不同，则递归检查左子树
        if (isSubtree(root.left, subRoot)) {
            return true;
        }

        // 如果左子树中没有找到 subRoot，则递归检查右子树
        if (isSubtree(root.right, subRoot)) {
            return true;
        }
        return false;
    }
    public boolean commpare(TreeNode p, TreeNode q){
        if (p == null && q == null){
            return true;
        }
        if (p == null || q == null || p.val != q.val){
            return false;
        }
        boolean left = commpare(p.left, q.left);
        boolean right = commpare(p.right, q.right);
        return left && right;
    }
}
